---
title: "5、宝石组合"
created: 2025-11-28
tags:
  - 算法
---

# 5、宝石组合

## 题目 宝石组合

![[image-b6fd1163.png]]

## 思路分析

这题不应该

我公式推错了

gcd(a,b,c)=gcd(gcd(a,b),c)

lcm(a,b,c)=lcm(lcm(a,b),c)

lcm(a,b)=a\*b/gcd(a,b)

结果三个数的lcm我却一下子脑子瓦特了 写成了a\*b\*c/gcd(a,b,c)

唉

## 代码实现

```cpp
 /*
n枚宝石 颜色形状闪亮度 主要是闪亮度
//第i枚宝石的闪亮度为 Hi
从N枚中选3枚进行组合 dfs组合型枚举？ N到1e5 不行

组合后的计算
lcm= (a*b)/gcd(a,b)
//int lcm1(int a,int b){
//	return (a*b)/__gcd(a,b);
//}
//int lcm2(int a,int b,int c){
//	int temp=__gcd(a,b);
//	temp=__gcd(temp,c);
//	return (a*b*c)/temp;
//}
涉及除法 不能用除之后的数继续算 把HaHbHc移上去 先乘后除
//公式化简成 gcd(a,b)*gcd(a,c)*gcd(b,c)
//           --------------------------
//                 gcd(a,b,c)

H值升序后字典序最小的方案 也就是先找到的方案
这案例 怎么会是123
lcm(a*b*c)！= a*b*c/gcd(a*b*c) 错了
*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=1e5;
int h[N];
int path[4];
int ans[4];
int n;
LL res=-0x3f3f3f;
bool check(int a,int b,int c){
	int temp=__gcd(a,b);
	temp=__gcd(temp,c);
	int val=(__gcd(a,b)*__gcd(a,c)*__gcd(b,c))/temp;
//	cout<<"last: "<<res<<"now "<<val<<endl;
	if(val>res){
		res=val;
		return true;
	}
	else
		return false;
}

void dfs(int u,int start){
	if(u>3){
//		for(int i=1;i<=3;i++)
//			cout<<path[i]<<" ";
//		cout<<endl;
		int a,b,c;
		a=path[1],b=path[2],c=path[3];
//		cout<<a<<" "<<b<<" "<<c<<endl;
		if(check(a,b,c)){
			for(int i=1;i<=3;i++){
				ans[i]=path[i];
			}
		}
		return;
	}
	for(int i=start;i<=n;i++){
		path[u]=h[i];
		dfs(u+1,i+1);
		path[u]=0;
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	dfs(1,1);
	for(int i=1;i<=3;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[4、R格式|4、R格式]] 🏠 [[00-刷题理模型]] ➡️ [[6、数字接龙|6、数字接龙]]